Indexes are often used in relational database management systems to improve performance when accessing (reading or writing) data contained in relational tables stored in the database management system. An index (typically in the form of an index table) stores data values (of a column in a base relational table) and pointers to the rows in the base relational table where those data values occur. An index table can be arranged in ascending or descending order (or some other defined order such as a hash order) so that the database management system can quickly search the index table to find row(s) containing a particular data value for a given column. A database management system can then follow the pointer(s) contained in the index table to locate the row (or rows) containing the data value. An index can also be defined on multiple columns (instead of just one column) of a base table.
Typically, indexes are defined on predefined data types that are supplied by database software executable in a database management system. Examples of predefined data types include an integer data type, character data type, and so forth. With more recent developments in database technology, relational tables are able to store data of other types, such as spatial geometry, image, audio, video, and other forms of more complex data. The storage of more complex data types in relational tables has been enabled by SQL: 1999 (or SQL3), which supports user-defined data types (UDTs).
UDTs allow a user of database software to specify the data type (other than data types offered with the database software) that is to be used to store data. For example, a spatial geometry data type can be defined to store map data, a video data type can be defined to store video data (e.g., movies), an audio data type can be defined to store audio files (e.g., music files), an image data type can be defined to store pictures, a text data type can be defined to store documents (e.g., Word documents), and so forth.
Conventionally, efficient techniques have not been provided to define indexes for complex data types that are UDTs. Although the database software vendor or manufacturer can invest engineering resources to define various types of formats for storing indexes for UDTs, such an investment of engineering resources is associated with substantial costs. Moreover, the database software vendor is typically unable to address all possible UDTs that can be created by users of the database software. The result is that even after substantial investments of resources by the database software vendor to create different formats for indexes on various UDTs, the database software would still not be able to provide the desired level of flexibility in providing indexes for data types not considered by the database software vendor.